1. Field of the Invention
This invention relates to methods and apparatus for digital addition, and in particular to methods and apparatus for "carrying" in digital addition, and a method for designing carry circuits.
2. The Prior Art
Digital addition processes must provide a method for "carrying" when the capacity of a column is exceeded. For example, in a decimal system for adding two numbers, when the result of additions in a column exceeds nine, a one must be carried to the next column. Also, for every column except the lowest ordered one, provision must be made for receiving a number carried from the preceeding lower order column. The carry operation occurs frequently in addition.
Consider adding two binary numbers, A and B. A representation of these numbers uses a subscript to denote the position or column of the bit in the number. The units position of A is A.sub.0, the twos position of A is A.sub.1, the fours position of A is A.sub.2 the eights position of A is A.sub.3, and in general, the 2.sup.k th position of A is denoted A.sub.k. The essence of an adder is to combine the two bits A.sub.k and B.sub.k with the carry into the kth position C.sub.k from the next lower order position k-1 to produce the sum bit S.sub.k. The sum bit is thus EQU S.sub.k =A.sub.k .sym.B.sub.k .sym.C.sub.k ( 1)
where .sym. represents the logical EXCLUSIVE OR function. Combining A.sub.k and B.sub.k as A.sub.k .sym.B.sub.k is straight forward, since A.sub.k and B.sub.k are immediately available. Obtaining and combining C.sub.k as required by equation (1) is more difficult since it depends on the results of all the additions of lower order bits i&lt;k. Generating the carries into each position is therefore the challenge of adder design.
One of the simplest forms of adders is the ripple-carry adder in which a single carry from one column to the next is provided at each level, starting with the lowest order column. Although simple, the ripple-carry adder is relatively slow because of the relatively large number of levels or stages required. Since the circuits of one level cannot do their operations until those of the previous level have completed theirs, the time required for addition is generally determined by the number of levels.
One technique which has been employed to expedite addition separates the function of simple addition from that of the calculation of the carry bits. Probably the most common example today is the carry look-ahead adder. The standard carry look-ahead adder circuitry is obtained by considering the Boolean functions that define addition and applying a little algebra to them (see Computer System Architecture, first edition, 1976, M. Morris Mano, Prentice-Hall, pages 242-249). In this process, two Boolean terms are usually introduced, called generate and propagate. The carry look-ahead method of addition has been standard for many years with only minor changes. (See The TTL Data Book, volume 2, Texas Instruments, 1985, pages 3-721 to 3-726 and the F100K ECL Data Book, Fairchild, 1982, pages 3-146 to 3 -151).
Another type of potentially fast adder circuit is the conditional-sum adder described in Conditional Sum Addition Logic by J. Sklansky, IRE Transactions on Electric Computers, Jun. 1960, pages 226-231. Two sum-and-carry pairs are computed for each column: one under the assumption that the carry into each column is zero and the other under the assumption that the carry into each column is one. In the last stage, the sums and final carries which are produced are no longer "conditional."